#include<iostream>
#include<string>
#include<stdio.h>
#include<stdlib.h>
#include<vector>
#include<unordered_map>
#include<algorithm>
using namespace std;
/*
* vector:翻译为向量, 矢量, 动态数组(数据结构中的顺序表)。
标准库类型 vector 是顺序容器的一个模板类，该容器将元素以线性排列方式进行存放，并且允许快速随机访问任何元素。
它是随机访问性能最佳的首选序列容器。可以看着是智能版的数组(能自动初始化,自动分配内存,自动回收内存,自动提供高效的服务)。
其中所有元素的类型都相同,可以通过下标(索引)访问数据。*/

/*
1.动态数据集合：当你不确定数据集的大小，或者数据集的大小会随时间变化时，vector 是理想的选择。例如，在处理用户输入或读取文件数据时，vector 可以根据需要动态地增长。
2.高效的随机访问：如果你需要快速访问元素（例如，在数组中随机访问元素），vector 提供了常数时间复杂度（O(1)）的随机访问能力。
3.替代数组：在 C++ 编程中，vector 通常被用来替代传统的固定大小数组，因为它更加灵活，自动管理内存，并提供了许多便利的功能（如自动扩容、迭代器支持等）。
4.数学和科学计算：在科学计算、物理模拟、数学建模等领域中，vector 用于存储和操作大量数值数据，如矩阵的行或列。
5.游戏开发：在游戏开发中，vector 可用于存储游戏对象、粒子、坐标点等动态集合。
6.图形处理：在图形处理程序中，vector 可以用来存储像素数据、顶点信息、纹理坐标等。
7.缓冲区：vector 可以作为缓冲区来临时存储数据，例如网络应用中的数据包缓冲或文件读写操作。
8.容器的容器：在需要存储其他容器（如 vector<vector<int>> 用于二维数组）时，vector 也是一个不错的*/






//容器可以使用变量作为数组的长度
/*vector v 的成员函数
含义
v.assign()
重新赋值数据
v.empty()
判断是否为空
v.size()
返回v的数据个数 (常用) 有效数据个数
v.capacity()
返回v当前的容量.这个函数作用不大
v.front()
返回第一个元素的引用
v.back()
返回最后一个元素的引用
v.insert()
插入一个或多个元素
v.erase()
删除一个或多个元素
v.push_back()
尾插
v.pop_back()
尾删
v.swap()
交换两个vector的值
v.clear()
清空数据
v.resize()
指定数据个数
v.shrink_to_fit()
容量紧缩


*/


//定义和初始化vector对象
//vector 是一个模板类，使用时需要提供具体的类型

//int main()
//{
//	vector<int>v = { 1,2,3,4,5 };
//	vector<double>v2 = { 12.3,43.3 };
//	vector<string>v3{ "fd","fd" };
//	for (auto x : v)
//		cout << x << " ";
//	cout << endl;
//
//	for (auto x : v2)
//		cout << x << " ";
//	cout << endl;
//	
//	for (auto x : v3)
//		cout << x << " ";
//	cout << endl;
//}


//向vector 对象中添加元素
//最常见的做法是定义一个空的(也可以不是空的)vector ,利用尾插函数push_back
//int main()
//{
//	vector<int> v = { 1,2,3 };
//	for (int i = 0;i < 3;i++)
//	{
//		v.push_back(i);
//	}
//	for (auto x : v)
//		cout << x << " ";
//	cout << endl;
//}


/*
*
v2=v1
把v1的数据全部赋值给v2
v1==v2
判断是否相等,索引元素相等
v1!=v2
判断是否不相等
<,<=,>,>=
判断大小关系,从头到尾依次比较
v1[i]
返回v1第i个元素的引用,从0开始
注意:vector对象不能 + ,不能通过 << 整体输出所有数据,需要用循环输出。

*/




//size() 成员函数 ：顺序表中的有效个数
//capacity 成员函数 ： 顺序表中的总容量

//int main()
//{
//	vector<int>v;
//	for (int i = 0; i < 20; i++)
//	{
//		v.push_back(i);
//		cout << "v的size:" << v.size() << ",v的容量:" << v.capacity() << endl;
//	}
//	return 0;
//}
//
//说明:不同平台容器容量增长的速率是不一样的, 有的增速是1.5倍, 有的是2倍。



//insert 函数
//在指定为之插入一个或者多个元素

//insert(位置（迭代器）, 几个，插入值）

//输出函数
//void Show(const vector<int>& v)
//{
//	for (const auto& x : v)
//		cout << x << " ";
//	cout << endl;
//}
//
//
//int main()
//{
//	vector<int>v1{ 1,2,3 };
//	Show(v1);
//
//	//插入一个值
//	v1.insert(v1.begin() + 1, 10); //迭代器的第二个位置
//	Show(v1);
//
//	//插入多个重复的值
//	v1.insert(v1.begin() + 2, 4, 20);
//	Show(v1);
//
//	//插入多个不同的值
//	vector <int> v2{ 1,2,3,4,5 };
//	vector <int> v3{ 100, 200, 300 };
//	v2.insert(v2.begin() + 1, v3.begin(), v3.end());//在v2的第二个位置插入v3的所有值
//	cout << "v2:";
//	Show(v2);
//}



//erase 删除一个或者多个值
//void Show(const vector<int>& v)
//{
//	for (const auto& x : v)
//		cout << x << " ";
//	cout << endl;
//}
//int main()
//{
//	vector<int>v{ 1,2,3,4,5 };
//	Show(v);
//
//	//删除第一个元素
//	v.erase(v.begin()); //删除第一个元素
//	Show(v);//2 3 4 5
//
//	//删除多个元素
//	//vs都是左闭右开的
//	v.erase(v.begin() + 1, v.begin() + 3);//删除第二个到第四个（不包含）
//	Show(v);//2  5
//
//	return 0;
//
//}
//注意:vector对象(以及string对象)的下标运算符可用于访问已经存在的元素, 而不能用于添加元素


//容器的长度可以使用变量
//int main()
//{
//	int n;
//	cin >> n;
//	vector<int>v{ n };//把n给v
//	cout << v.size() << endl;
//	for (auto i : v)
//		cout << i << " ";
//	return 0;
//}
//






//两数之和中，可以把vector作为返回值的类型
//vector<int> twoSum(vector<int>& nums, int target)
//{
//	int high = nums.size()-1; //右下标
//	for (int i = 0;i < nums.size() ;i++)
//	{
//		for (int j = i + 1;j < nums.size();j++)
//		{
//			if (nums[i] + nums[j] == target)
//				return { i,j };
//		}
//	}
//	return {};
//}
//int main()
//{
//	vector<int>v{ 12,3,4,5,2,4 };
//	int target = 7;
//	cout << "vector的长度是" << v.size() << endl;
//	auto v2 = twoSum(v, target);
//	cout << "下标是：";
//	for (auto i : v2)
//		cout << i << " ";
//	cout << endl;
//	return 0;
//}
//



//容器嵌套容器
//int main()
//{
//	vector<vector<int>>v; //容器里面放入容器
//	vector<int>v1;
//	vector<int>v2;
//	vector<int>v3;
//	vector<int>v4;
//
//	for (int i = 0;i < 4;i++)
//	{
//		v1.push_back(i + 1);
//		v2.push_back(i + 2);
//		v3.push_back(i + 3);
//		v4.push_back(i + 4);
//	}
//	//将容器元素插入到vector中
//	v.push_back(v1);
//	v.push_back(v2);
//	v.push_back(v3);
//	v.push_back(v4);
//
//
//	//注意想要把容器里面的容器都输出出来，需要两个for循环
//	for (auto it = v.begin();it != v.end();it++)
//	{
//		for (auto it2 = (*it).begin();it2 != (*it).end();it2++) {
//			cout << *it2 << " ";
//		}
//		cout << endl;
//	}
//	return 0;
//}
//




//1122. 数组的相对排序  error ???
vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) {
    //定义一个哈希表：统计每种字符出现的次数
    unordered_map<int, int>m;
    for (auto i : arr1)
    {
        m[i]++;
    }
    //在arr1中出现了几次，把它放入到arr2当中
    //处理在arr1中出现的元素
    vector<int>ans;
    for (auto x : arr2)
    {
        for (int i = 0;i < m[x];i++)
        {
            ans.push_back(x);
        }
    }
    //处理没有出现的元素
    //从arr1中找arr2的元素，找到的就删除
    for (auto i : arr2)
    {
        auto it = find(arr1.begin(), arr1.end(), i);
        while (it != arr1.end())
        {
            arr1.erase(it);
        }
    }
    sort(arr1.begin(), arr1.end());
    for (auto i : arr1)
    {
        ans.push_back(i);
    }

    return ans;
}

//int main()
//{
//    vector<int>arr1{2, 3, 1, 3, 2, 4, 6, 7, 9, 2, 19};
//    vector<int>arr2{ 2, 1, 4, 3, 9, 6 };
//    auto v=relativeSortArray(arr1, arr2);
//    for (auto i : v)
//        cout << i << " ";
//    cout << endl;
//}


//#include <iostream>
//#include <vector>
//#include <algorithm>
//
//int main() {
//    std::vector<int> vec = { 1, 2, 2, 3, 3, 3, 4, 5, 5 };
//
//    // 使用 std::unique 来删除重复元素
//    auto new_end = std::unique(vec.begin(), vec.end());
//
//    // 使用 erase 函数擦除重复元素
//    vec.erase(new_end, vec.end());
//
//    // 输出结果
//    for (int i : vec) {
//        std::cout << i << " ";
//    }
//    std::cout << std::endl;
//
//    return 0;
//}



//remove函数
void Show(vector<int>& v)
{
    for (auto x : v)
    {
        cout << x << " ";
    }
    cout << endl;
}
//int main()
//{
//    vector<int>v{ 1,2,3,4,5,1,1,1,1 };
//    cout << "原始数据： " << endl;
//    Show(v);
//
//    //移除所有值为1的元素
//    auto it = remove(v.begin(), v.end(),1);//要接受值
//    cout << "移除1后   ";
//    Show(v);
//
//    //删除无效元素
//    v.erase(it, v.end());
//    cout << "删除无效原始，v";
//    Show(v);
//
//
//    return 0;
//}